package com.ywk.base.dataStructure.search;

import java.util.Arrays;
//斐波那契查找
public class FibonacciSearch {

	public static void main(String[] args) {
		int[] nums= {1,3,6,8,10,15,19,24};
		//System.out.println(Arrays.toString(fib()));
		System.out.println("index="+fibSearch(nums, 3));
	}
	
	public static int fibSearch(int[] nums,int key) {
		int low=0;
		int hight=nums.length-1;
		int mid=0;
		int k=0;//f[k]表示范围个数，即当前比较的数组中元素的个数
		int[] f=fib();
		while(hight>f[k]) {
			k++;
		}
		//当数组长度未满足黄金分割数，对数组进行扩容
		int[] temp=Arrays.copyOf(nums, f[k]);//f[k]表示数组长度
		//扩容后，将数组后面值为0的数初始化为原数组中最大的数（即最后面的数）
		if(hight<f[k]) {
			for (int i = hight+1; i < temp.length; i++) {
				temp[i]=temp[hight];
			}
		}
		while(low<=hight) {
			mid=low+f[k-1]-1;
			if(key<temp[mid]) {
				hight=mid-1;
				k--;
			}else if(key>temp[mid]){
				low=mid+1;
				k-=2;
			}else {
				if(mid<hight) {
					return mid;
				}else {
					return hight;
				}
			}
		}
		return -1;
	}
	
	public static int[] fib() {
		int[] f=new int[20];
		f[0]=1;
		f[1]=1;
		for (int i = 2; i < f.length; i++) {
			f[i]=f[i-1]+f[i-2];
		}
		return f;
	}
}
